#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#define FOR(i,a,n) for(int i=a,_n(n);i<_n;++i)
#define REP(i,n) FOR(i,0,n)

const int inf = 1<<29;

using namespace std;


int map[501][501];
int Stoer_Wagner(int n)
{
    int ans = inf;
    vector<bool> done(n,false);
    REP(cnt,n-1)
    {
        vector<int> w(501,0);
        vector<int> res;
        REP(i,n) if(!done[i]) res.push_back(i);
        int s = -1,t = -1;
        REP(i,n-cnt)
        {
            int tmax = -1 ,next = 0;
            int pos = 0;
            REP(i,res.size()) if(w[res[i]]>tmax)
            {
                tmax =  w[next = res[i]];
                pos = i;
            }
            res.erase(res.begin()+pos);
            s = t , t = next;
            REP(i,res.size())
                w[res[i]]+=map[next][res[i]];
        }
        done[t] = true;
        REP(i,n) if(!done[i])
        {
            map[s][i] += map[t][i];
            map[i][s] += map[i][t];
        }
        ans = min(ans,w[t]);
    }
    return ans;

}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        REP(i,n+1) REP(j,n+1) map[i][j] = 0;
        REP(i,m)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]+=c,map[b][a]+=c;
        }
        cout<<Stoer_Wagner(n)<<endl;
    }
	return 0;
}
